// lookup_sorted_vector_h.h
//

#if !defined(LOOKUP_SORTED_VECTOR_H)
#define LOOKUP_SORTED_VECTOR_H

#include <vector>
#include <utility>
#include "components/stlhelper.h"

template <typename FUNC, typename T, unsigned BITS>
struct op_left_shift
{
	FUNC op;
	unsigned operator()(const T& t)
	{
		return op(t) >> BITS;
	}
};

template <typename FUNC, typename T, unsigned BITS>
struct cmp_left_shift
{
	op_left_shift<FUNC, T, BITS> op;
	unsigned operator()(const T& t1, const T& t2)
	{
		return op(t1) < op(t2);
	}
};

template <unsigned BITS, typename T, typename ForwardIter, typename HASH>
void create_vector_hash_index(ForwardIter data_iter, ForwardIter data_last,
								std::vector<std::pair<ForwardIter, ForwardIter> >& index,
								HASH)
{
	op_left_shift<HASH, T, BITS> hash_and_shift;

	assert(stlhelper::is_sorted(data_iter, data_last, cmp_left_shift<HASH, T, BITS>()));
	
	// create index and initialize with absent flag
	std::vector<std::pair<ForwardIter, ForwardIter> > new_index(1 << (32 - BITS));
	std::pair<ForwardIter, ForwardIter> absent(data_iter, data_iter);
	std::fill(beg_to_end(new_index), absent);
	index.swap(new_index);
	
	// empty index
	if (data_iter == data_last)
		return;

	// initialize starting position
	unsigned prev_hash = hash_and_shift(*data_iter++);
	ForwardIter curr_start = data_iter;


	unsigned i = 0;
	while (data_iter < data_last)
	{
		unsigned curr_hash = hash_and_shift(*data_iter);
		if (curr_hash == prev_hash)
		{
			data_iter++;
			continue;
		}
		
		// if hash has changed, on a new interval:
		//		save range and set the next start to the end of the range
		index[prev_hash]	= std::make_pair(curr_start, data_iter);
		prev_hash			= curr_hash;
		curr_start			= data_iter++;
	} 	

	// save last pair
	index[prev_hash]		= std::make_pair(curr_start, data_iter);

}


template<unsigned BITS, typename ForwardIter, typename Tp, typename HASH, typename FUNC>
    std::pair<ForwardIter, ForwardIter>
    indexed_equal_range(const Tp& val,
						std::vector<std::pair<ForwardIter, ForwardIter> >& index,
						HASH, FUNC func)
{
	op_left_shift<HASH, Tp, BITS> hash_and_shift;
	unsigned hash = hash_and_shift(val);

	return std::equal_range(index[hash].first, index[hash].second, val, func);
}

template<unsigned BITS, typename ForwardIter, typename Tp, typename HASH>
    std::pair<ForwardIter, ForwardIter>
    indexed_equal_range(const Tp& val,
						std::vector<std::pair<ForwardIter, ForwardIter> >& index,
						HASH)
{
	op_left_shift<HASH, Tp, BITS> hash_and_shift;
	unsigned hash = hash_and_shift(val);

	return std::equal_range(index[hash].first, index[hash].second, val);
}

#endif
